class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class Solution: # 时间复杂度是O(m+n)，空间复杂度是O(1)
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None

        p1, p2 = headA, headB
        while p1 != p2: 
            p1 = p1.next if p1 else headB # 如果p1走到头了，则从头开始走p2
            p2 = p2.next if p2 else headA # 如果p2走到头了，则从头开始走p1
        return p1 # 两个指针如果有交点就一定会相遇，因为p1走的路程是a+c+b，p2走的路程是b+c+a，如果有交点，则两者的路程一定相同

# 构建链表的辅助函数
def buildLinkedList(values):
    dummy = ListNode(0)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

# 构建相交链表
def createIntersectingLists(intersectVal, listA_vals, listB_vals, skipA, skipB):
    headA = buildLinkedList(listA_vals)
    headB = buildLinkedList(listB_vals)

    currA = headA
    for _ in range(skipA):
        currA = currA.next

    currB = headB
    for _ in range(skipB):
        currB = currB.next

    # 链接B链表的skipB位置到A链表的skipA位置
    currB.next = currA

    return headA, headB

if __name__ == '__main__':
    # 测试数据
    intersectVal = 8
    listA_vals = [4, 1, 8, 4, 5]
    listB_vals = [5, 6, 1, 8, 4, 5]
    skipA = 2
    skipB = 3

    headA, headB = createIntersectingLists(intersectVal, listA_vals, listB_vals, skipA, skipB)

    s = Solution()
    intersection = s.getIntersectionNode(headA, headB)

    if intersection:
        print(f"Intersected at '{intersection.val}'")
    else:
        print("No intersection")
